package top.dprkshow.practice.graph;

/**
 * @author Kent HAN
 * @date 2021/9/13
 */
public class Cycle2 {
    private boolean hasCycle;
    private boolean[] visited;
    private int[] parent;

    public Cycle2(MatrixGraph g) {
        hasCycle = false;
        visited = new boolean[g.getTotalVertices()];
        parent = new int[g.getTotalVertices()];
    }

    public void init(MatrixGraph g) {
        for (int i = 0; i < g.getTotalVertices(); i++) {
            if (!visited[i]) {
                dfs(g, i);
            }
        }
    }

    private void dfs(MatrixGraph g, int vertex) {
        visited[vertex] = true;
        for (Integer adjVertex : g.adj(vertex)) {
            if (!visited[adjVertex]) {
                parent[adjVertex] = vertex;
                dfs(g, adjVertex);
            } else if (adjVertex != parent[vertex]) {
                hasCycle = true;
            }
        }
    }
}
